MacHack 1996/MacHack 1996.toast/Presentations/Presentations ’96/Sessions ’96/Random Numbers/Random.c

Text File | 1996-06-03 | 10.8 KB | 331 lines | [TEXT/CWIE]

//
// Two-Stage Cryptographic Random Number Generator
//
// Copyright © 1996, Jon Callas, Eldacur Technologies. All Rights Reserved.
//
// You have permission to use this code in any commercial or non-commercial programs provided
// you do the following:
//
// (1) Somewhere in your documentation, about box, etc. you state that you use Jon Callas's
//     Two-Stage Random Number Generator and that it is copyright by him.
// (2) If you use it in a commercial product, you send me email at [e-mail] telling me
//     that you're using it. I don't have any nefarious purposes, I'm not going to sell your
//     name to some mailing list, I just want to know who is using it, so I can send updates
//     to you and be able to brag about the bizillion people that use this.
// (3) If you find bugs, make substantive improvements, etc. that you make a best-faith effort
//     to send them to me so I can incorporate it into the code.
//
// That's it. That's all you have to do. It's not much to ask. It's not as odious as a copyleft
// so why not do it?
//

#include "Random.h"

#ifdef COMPILE_COMMENTS

What this is:

This is a high-quality random number generator that can create large amounts of good random
numbers. When used properly, it can hold up to 2048 bits of randomness, or entropy in it. This
is more than enough for any purpose you need to use it for. However, like any piece of
precision machinery, it must be used properly and handled with care.

Please take the care to read these instructions and follow them.

HOW TO USE IT
--- -- --- --

The base object type is a Randomizer. There are also objects here for the two stages, the
Distiller and the Grinder. They'll be explained below. Usually you don't ever have to use them.

(1) Make a Randomizer. The statement:

    Randomizer *r = new Randomizer();

is good enough.

(2) Find a source of random inputs. Real random inputs. Best things to use are user-driven
inputs like mouse positions, timings of keystrokes, and stuff like that. Each observation you
seed the Randomizer with should have a guess of how random it is, in decibits. Yeah, decibits.
Tenths of bits. If you think it's as good as a coin toss (like the clock time), then it should
be 10. If it's a really mediocre observation, use 1. If it's junk that you're using because
you like it (like your ethernet address, contents of files, etc.) throw it into the mix, but
rate it 0. It all gets mixed up into the first stage, the Distiller. Hint: Always Guess Low,
Especially If You Are Writing Privacy Software! Once the Distiller is filled with enough
entropy, it will empty itself into the second stage. You can force the Distiller to empty
by using a negative number for your entropy guesss.

Add in seed values with:

    r->AddSeed(sourcePtr, length, decibits);

For example, you'd add in a timing observation with:

    r->AddSeed(&timer, 4, 10);

You can find out how much entropy is in the system with the call:

    r->GetEntropy();

(3) You should make a habit of periodically adding stuff to the mix. Sample the mouse and put
X,Y position in. Time how long it takes you to create, write garbage into, and delete a 1MB
file. Have fun. If you are in the habit of using a variety of observations, and mixing them in
to the Randomizer, the accumulated entropy will help your system be random. And remember, when
you guess about your randomness, guess low, especially in the things you gather in the
background!

(4) Get random values with these functions:

    r->Byte(); r->Word(); r->Long();

These return a random 8, 16, and 32 bit quantity respectively. The function:

    r->String(char *position, long size);

will fill the memory 'size' long pointed to by 'position' with random bytes.

(5) Saving State:

If you need to save the state of the Randomizer, you can call:

    r->GetState(RandomState *state);
    r->SetState(RandomState *state);

to save and restore the state. You should consider the state of the randomizer to be sensitive
data! Treat it with the same respect you would treat password files, private keys, and other
sensitive data. Don't let an adversary break your privacy system by scamming your random
numbers!


HOW IT WORKS
--- -- -----

Stage 1 is the Distiller. It is a cryptographic checksum, specifically the Secure Hash Algorithm.
The implementation of SHS I use here was written by Paul Kocher, given to me by Paul, and used with
his kind permission.

A cryptographic checksum like this can be used to accumulate entropy. There is a problem when you
toss together things you think are random. The problem is that they probably aren't as random as
you think they are, and they probably aren't random in the way you think they are. The wonderful
thing about a checksum like this is that it can distill all the entropy in your samples. It doesn't
increase entropy, but it holds it up to its maximum (in the case of SHS, 160 bits). It can even be
used in things that are weakly random.

An example of a weakly random source follows: Suppose you were sampling white noise from a
microphone in the lab you put your HoozieServer 2000 in. Let's also suppose that while it
just sounds like hiss to you, if we do fourier analysis on the samples we find that it's all
just a bunch of harmonics except for some small bit of noise that makes your sample be X mod Y
one time in four, and A mod B the other three times in four. Depressing, huh? It's not hopeless,
though. It does suck that you thought you were getting 16 bits of white noise on each sample of
the microphone, but there is still some value here. There's actually a half-bit of randomness in
any sample you make. Yeah, fractional bits sound weird, but they really represent the flip of an
off-kilter coin. You can still use them, so long as you don't overestimate their value.

This is why I tell you to make many samples, and always guess low. Murphy *is* out to get you.

Once you have accumulated enough entropy in the Distiller, we move it to the second stage of the
generator. I trust your guesses, when you tell me there's enough, I go for it. That's why I'm
being such a nag.

The second stage of the random number generator is a non-linear, arithmetic streamer. Its guts are
mathematically similar to some of the non-linear streams used in some high-performance
stream cyphers, but adapted to the needs of a random number generator, as opposed to a stream
cypher.

The combination of the two of them give you a way to hold up to 2048 bits of entropy and use it to
generate crypto-quality random numbers. If you use it properly, it will serve you well. If you
misuse it, don't come complaining to me.

If you need to know more about random numbers, what makes a good random number, why the rand()
function isn't good enough, or why things you think are random aren't, look at some of the
following sources:

Internet RFC 1750, available on a web site near you.
Bruce Schneier's "Applied Cryptography", available in fine bookstores everywhere.

#endif

//
// The Distiller object, the first stage generator
//
Distiller::Distiller()
{
    Init();                // Initialize the object
}

void Distiller::Init()
{
    // The only reason this routine exists, as opposed to
    // keeping it in the constructor is that I thought it might be
    // useful to be able to re-init an existing distiller.

    SetEntropy(0);
    shsInit(&shs);
}

int Distiller::AddData(void *start, long length, int decibits)
{
    totalEntropy += decibits;                            // Update the guess
    shsUpdate(&shs, (unsigned char *) start, length);    // Hash in the observation

    return totalEntropy;
}

void Distiller::GetHash(unsigned char hash[HASHLEN])
{
    SHS_CTX context = shs;                                // Make a copy of the hash state
    shsFinal(&context, hash);                            // Finalize the copied hash.
}

//
// This is the Grinder object, the second stage of the generator
//

Grinder::Grinder()
{
    numberPlace = 0;
    newPlace = 0;
    InitNums();
}

Grinder::Grinder(void *theStuff, long stuffLen)
{
    // We don't actually ever use this constructor, but here it is, in case
    // you want to make a Grinder and give it some stuff.

    numberPlace = 0;
    newPlace = 0;
    InitNums();
    AddStuff(theStuff, stuffLen);
}

void Grinder::InitNums()
{
    for (int i = 0; i < 256; i++)            // put the numbers 255 downto 0 into the array
        numbers[i] = ~i;
}

void Grinder::AddStuff(void *theStuff, long stuffLen)
{
    int             i;
    int             j = 0;
    int                stuffPlace = 0;

    for (i = 0; i < 256; i++)
    {
        j = (numbers[i] + ((unsigned char *) theStuff)[stuffPlace] + j);
        j &= 0xff;

        unsigned char t = numbers[i];                        // Swap the appropriate number
        numbers[i] = numbers[j];
        numbers[j] = t;

        stuffPlace = (stuffPlace + 1) % stuffLen;
    }

    for (i = 0; i < 256; i++)                        // Turn the crank through a complete
        Turn();                                        // revolution to thoroughly mix up the
                                                    // numbers. Studies show that this lessens
                                                    // the effect of weakly random stuff.
}

unsigned char Grinder::Turn()
{
    // The actual work is done here for the second stage. This is what
    // pops off random bytes. We spin this when we add more stuff to
    // stir it up.

    register unsigned char t;

    // We're going to swap two cells of stuff and numbers. We walk around the
    // array, picking the next spot. The place we're going to swap it with
    // is selected with the statements below:

    newPlace = newPlace + numbers[numberPlace];
    newPlace &= 0xff;    // mod 256

    t = numbers[numberPlace];                // Swap number cells
    numbers[numberPlace] = numbers[newPlace];
    numbers[newPlace] = t;

    t += numbers[numberPlace];                // Add in the other cell
    t &= 0xff;

    numberPlace = (numberPlace + 1) & 0xff;    // Find the next cell to play with

    return numbers[t];
}

void Grinder::GetRandom(void *thePlace, long length)
{
    unsigned char *x = (unsigned char *) thePlace;

    for (int i = 0; i < length; i++)                // Just step out N bytes
        *x++ = Turn();
}


unsigned char Randomizer::Byte()
{
    return Turn();
}

unsigned short Randomizer::Word()
{
    return (Turn() << 8) | Turn();
}

unsigned long Randomizer::Long()
{
    return    (Turn() << 24) |
            (Turn() << 16) |
            (Turn() <<  8) |
            Turn();
}

void Randomizer::AddSeed(void *seed, int seedLen, int entropyGuessInDecibits)
{
    if (entropyGuessInDecibits < 0)
        entropyGuessInDecibits = TOTALENTROPY;

    AddData(seed, seedLen, entropyGuessInDecibits);

    if (GetEntropy() > TOTALENTROPY)
    {
        unsigned char    hash[HASHLEN];

        GetHash(hash);
        AddStuff(hash, HASHLEN);

        SetEntropy(GetEntropy() - TOTALENTROPY);
    }
}

Randomizer::Randomizer()
{
    busy = 0;
}

void Randomizer::GetState(RandomState *state)
{
    state->distillerEntropy    = GetEntropy();
    state->numberPlace        = numberPlace;
    state->newPlace            = newPlace;
    state->still            = shs;

    for (int i = 0; i < 256; i++)
        state->numbers[i] = numbers[i];
}

void Randomizer::SetState(RandomState *state)
{
    SetEntropy(state->distillerEntropy);
    numberPlace        = state->numberPlace;
    newPlace        = state->newPlace;
    shs                = state->still;

    for (int i = 0; i < 256; i++)
        numbers[i] = state->numbers[i];
}